The M/G/1 is a classic queueing model: jobs of random size arrive randomly over time to a single server, which can serve one job at a time, with an infinite-capacity queue. The response time of a job is the total amount of time it spends in the system, including both waiting and service. A common goal of queueing system design is to minimize mean response time and related measurements. For a single-server system, the most important design decision is the scheduling policy, which decides which job to serve at each moment in time. Depending on the system parameters and whether each job's size is known or unknown, different scheduling policies may be optimal.

In this work we consider the problem of quantitatively analyzing mean response time and related metrics. State-of-the-art techniques require an ad-hoc analysis for each different scheduling policy. For example, the first-come, first-serve policy (FCFS) has a very different analysis than the shortest remaining processing time policy (SRPT). Some policies, such as the shortest expected remaining processing time policy (SERPT), have no known analysis. The difficulty lies in the fact that in SERPT, a job's priority might vary arbitrarily with time.

In this work, we introduce an extremely broad class of scheduling policies called SOAP: Schedule Ordered by Age-based Priority. SOAP policies include both virtually all previously analyzed policies, such as FCFS and SRPT, and a wide array of policies which have never been analyzed before, such as SERPT and the famously complex Gittins index policy. We present a universal response time analysis that applies all SOAP policies, unifying prior techniques and enabling analysis of previously intractable scheduling policies.

Paper: http://ziv.codes/pdf/sigmetrics2018-scully.pdf